package SortAlgorithm;

/**
 * @author gao
 * @date 2025/11/5 19:44
 */

public class ShellSort implements Sort {

    @Override
    public void sort(int[] nums) {
        // 初始化步长为数组长度的一半
        int gap = nums.length / 2;

        // 当步长大于0时，继续进行希尔排序
        while (gap > 0) {
            // 对当前步长进行插入排序
            shell(nums, gap);
            // 步长减半，继续进行排序
            gap /= 2;
        }
    }

    /**
     * 希尔排序中的插入排序方法
     * @param nums 待排序的数组
     * @param gap 当前步长（间隔）
     */
    private void shell(int[] nums, int gap) {
    // 从gap位置开始遍历数组
        for (int i = gap; i < nums.length; i++) {
        // 保存当前元素
            int tmp = nums[i];
        // 计算前一个步长元素的位置
            int j = i - gap;
        // 在步长间隔内进行比较和移动元素
            for (; j >= 0; j -= gap) {
            // 如果前面的元素大于当前元素，则将前面的元素后移
                if (nums[j] > tmp) {
                    nums[j + gap] = nums[j];
                } else {
                // 如果找到合适位置，退出循环
                    break;
                }
            }
        // 将当前元素插入到正确位置
            nums[j + gap] = tmp;
        }
    }
}